package cn.icatw.leetcode.editor.cn;
//给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
//
//
//
// 示例 1：
//
//
//输入：head = [1,2,2,1]
//输出：true
//
//
// 示例 2：
//
//
//输入：head = [1,2]
//输出：false
//
//
//
//
// 提示：
//
//
// 链表中节点数目在范围[1, 10⁵] 内
// 0 <= Node.val <= 9
//
//
//
//
// 进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
//
// Related Topics 栈 递归 链表 双指针 👍 1932 👎 0


import java.util.Stack;

//Java：回文链表
public class T234_PalindromeLinkedList {
    public static void main(String[] args) {
        Solution solution = new T234_PalindromeLinkedList().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public boolean isPalindrome(ListNode head) {
            if (head == null || head.next == null) {
                return true;
            }
            //利用栈
            Stack<Integer> stack = new Stack<>();
            //找到中间节点
            ListNode fast = head;
            ListNode slow = head;
            while (fast != null && fast.next != null) {
                stack.push(slow.val);
                fast = fast.next.next;
                slow = slow.next;
            }
            //如果是奇数个节点，slow再往前走一步
            if (fast != null) {
                slow = slow.next;
            }
            //比较
            while (slow != null) {
                if (stack.pop() != slow.val) {
                    return false;
                }
                slow = slow.next;
            }
            return true;

        }

    }

    //leetcode submit region end(Prohibit modification and deletion)
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
